package someTestExcemple.huaweiOd.string;

//华为OD机试 - 最小循环子数组（Java 2023 B卷 100分）
//https://blog.csdn.net/guorui_java/article/details/131721023
import java.util.*;
public class MinimumCircularSubarrayKMP {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取数组元素个数
        int n = scanner.nextInt();
        int[] nums = new int[n];
        // 读取数组元素
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        // 调用 findSmallestRepeatingSubarray 方法找出最小重复子数组
        int[] result = findSmallestRepeatingSubarray(nums);
        // 输出最小重复子数组
        for (int i = 0; i < result.length; i++) {
            if (i > 0) {
                System.out.print(" ");
            }
            System.out.print(result[i]);
        }
        scanner.close();
    }

    public static int[] findSmallestRepeatingSubarray(int[] nums) {
        int n = nums.length;
        // 遍历所有可能的子数组长度
        for (int len = 1; len <= n; len++) {
            //只有除得净才能循环
            if (n % len == 0) {
                boolean isRepeating = true;
                // 检查当前长度的子数组是否能重复拼接成原数组
                //todo 精髓对 len后面的对len取模
                for (int i = len; i < n; i++) {
                    if (nums[i] != nums[i % len]) {
                        isRepeating = false;
                        break;
                    }
                }
                if (isRepeating) {
                    // 若能重复拼接，则返回该子数组
                    int[] subarray = new int[len];
                    System.arraycopy(nums, 0, subarray, 0, len);
                    return subarray;
                }
            }
        }
        return nums;
    }
}
